UVa/11450 - Wedding shopping/11450.2.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <stdio.h>
   5 #include <iostream>
   6 #include <vector>
   7 #include <algorithm>
   8
   9 using namespace std;
  10
  11 int main(){
  12   int N;
  13   scanf("%d", &N); //cin >> N;
  14   while (N--){
  15     int T, C;
  16     scanf("%d %d", &T, &C); //cin >> T >> C;
  17     vector< vector<int> > w;
  18     for (int i=0; i<C; ++i){
  19       int K;
  20       scanf("%d", &K); //cin >> K;
  21       vector<int> row(K);
  22       for (int j=0; j<K; ++j){
  23         scanf("%d", &row[j]);//cin >> row[j];
  24       }
  25       w.push_back(row);
  26     }
  27
  28     bool dp[T+1][C];
  29     memset(dp, 0, sizeof dp);
  30
  31     for (int j=0; j<w[0].size(); ++j){
  32       dp[w[0][j]][0] = true; //Primer nivel
  33     }
  34
  35     for (int i=1; i<C; ++i){
  36       for (int t=0; t<=T; ++t){
  37         for (int j=0; j<w[i].size(); ++j){
  38           if (t - w[i][j] >= 0){
  39             if (dp[t-w[i][j]][i-1]){
  40               dp[t][i] = true;
  41               break;
  42             }
  43           }
  44         }
  45       }
  46     }
  47
  48     bool solved = false;
  49     for (int t=T; t>=0; --t){
  50       if (dp[t][C-1]){
  51         printf("%d\n", t);//cout << t << endl;
  52         solved = true;
  53         break;
  54       }
  55     }
  56
  57     if (!solved){
  58       printf("no solution\n");//cout << "no solution" << endl;
  59     }
  60   }
  61   return 0;
  62 }